
\documentclass{report}
\usepackage[frenchb]{babel}
\usepackage[utf8x]{inputenc}
\title{Système de cache HTTP distribué pour réseaux informatiques maillés, instables, et à forts temps de latence.}
\author{Christopher Glass}

%\usepackage[pdftex]{hyperref}
\usepackage[pdftex,bookmarks,colorlinks]{hyperref}
\begin{document}


\maketitle


\tableofcontents

\chapter[Mandat]{Mandat}
Les réseaux informatiques dans les pays émergeants souffrent encore de multiples coupures, ainsi que de temps de latence et de bandes passantes limitées, dues au coût de la mise en place d'infrastructures aux normes européenes.

\chapter[Cahier des charges]{Cahier des charges}

\section[Bande passante]{Bande passante}
\label{CahierDesCharges}
La bande passante limitée est le problème principal que ce logiciel tente d'amoidrir. 

Dans le cadre d'un enseignement, on suppose qu'une majorité des sites consultés sont consultés par non pas un étudiant, mais par plusieurs. Au lieu d'aller chercher le contenu du site (images, textes, mise en page\ldots) une fois par étudiant, le but d'un cache est de n'aller checher le contenu qu'une seule fois depuis le site distant, de le stocker au sein du reseau local (généralement plus fiable et plus rapide), et de le servir aux differents clients de facon efficace, sans utiliser la ressource la plus rare – la bande passante externe.

Dans la mesure ou le réseau national est en général moins rare que le réseau international, le cache ira chercher un objet chez ses pairs (d'autres caches dont il connait l'addresse), qui feront de même, jusqu'a ce qu'un niveau de parcours d'arbre soit atteint, auquel cas le dernier noeud atteint attachera un header HTTP spécifique a son ultime requête, et les noeuds suivants de feront que relayer sa demande jusqu'au site final, puis rafaichirons leur cache avec la réponse.

Il est indispensable de pouvoir parametrer un niveau de récursion (profondeur de recherche dans l'arbre recouvrant du reseau de noeuds).

Le cache doit permettre de facilement modifier le type d'objets mis en cache, le type d'objets a exclure, ainsi que les protocoles / ports a utiliser.

\section[Latence]{Temps de latence}
La latence \footnote{Temps entre l'émission de la requête et la récéption de la réponse} est généralement élevée dans les pays en voie de développment. Il est courant de n'avoir qu'un accès national unique au réseau mondial (backbones océaniques). Le temps de réponse peut donc significativement déteriorer les conditions d'utilisation du réseau.
2.Le cahce n'utilisera pas de protocole spécifique pour synchroniser les caches entre eux, dans le but de ne pas utiliser la bande passante inutilement.

\section[ressources]{Ressources système}

Les machines a disposition dans les pays en voie de dévelopment sont souvent issues de récupèration, c'est a dire d'envoi de machines occidentales désuettes. Elles sont donc par définition moins performantes que celles dont nous disposons dans un pays industrialisé.

Le temps processeur limité implique des algorithmes performants a tout les niveaux. On fera attention a la complexité théorique ainsi qu'au cout réel de chaque opération.

L'espace disque utilisable doit pouvoir etre configuré facilement. Le temps d'accès au cache doit etre linéaire, indépendement de la taille sur disque. Le cache sera persistant.

De même l'espace mémoire doit être limitable par configuraiton.

\chapter[Solution]{Solution proposée}
\section[Choix techniques]{Choix techniques}
\subsection[Language de programmation]{Language de programmation}
Le choix se porte sur le Python, parce qu'il présente un certain nombre d'avantages intéressants:

\begin{description}

\item [Puissance:] Python est un language orienté-objet de haut niveau permetant la production de code concis, et facile a apréhender. Il permet en outre d'enseigner la programmation de façon iterative, sans changer de language: Commencer par de la programmation procédurale, puis retravailler le code pour le rendre \emph{orienté-objet}, puis finalement introduire des notions de programmation de haut niveau (récursion, \emph{lambda-fonctions}, introspection, programmation dynamique, programmation concurrente, algorithmes distribués \ldots).

\item [Syntaxe stricte:] Python considère l'indentation comme un élément léxical. Le code python de n'importe quel programmeur au monde est donc indenté et formatté de la même facon, ce qui facilite grandement la comprehension d'un programme pour quelqu'un ayant déjà eu affaire a Python. Inversément, quelqu'un ayant déja eu affaire à Pyhton (dans le cadre d'un cours par exemple), pourra facilement comprendre et adapter un programme écrit en Python à ses besoins.

\item [``Batteries incuded'']: Python est fourni avec une librairie standard très vaste, et ne nécessite pas de faire appel a une ou des librairies externes pour une grande majorité de tâches.

\item [Vie active:] Python est le language de choix d'une vaste communauté. Un grand nombre de sociétés de développment logiciel contribuent activement a son évolution et a sa maintenance (Google, Vmware, Apple, Microsoft, SUN, IBM)

\item [Multi-plateformes:] Python est préinstallé sur dans de très nombreux systèmes d'exploitation (MacOS, Linux, Solaris, les BSD), et il est disponible en téléchargement pour de nombreux autres (Windows, AS400)

\item [Extensible:] Bien qu'étant un language de scripting (donc comportant un coût d'overhead), Python est aisément extensible et/ou optimisable avec C++, soit pour lui exposer une librairie non disponible dans la librairie standard, soit pour optimiser certains algorithmes (en les rendants spécifiques a un type de processeur pour qu'ils tirent parti des possibilités hardware, comme des instructions spécialisées par exemple)

\item [Documenté:] Python est livré avec une documentation extensive, et de nombreux tutoriaux de qualité exemplaire, faciles à apréhender, et souvent pleins d'humour (ce qui facilite l'apprentissage).

\end{description}


\subsection[Stockage des données]{Stockage des données}
\begin{description}
\item [Meta informations] Les méta informations seront stockées dans une base de données Sqlite. Il n'est pas nécéssaire d'avoir plus qu'un base de données embarquée pour ce projet, dans la mesure ou il ne nécéssite pas de gestion de concurrence d'accès.
\item[Données en cache] Les données en cache seront stockées dans le système de fichier. Cela offre plusieurs avantages: 
\begin{itemize}
\item Une structure en arbre déja existente
\item Une panoplie d'artifices permettant d'optimiser l'utilisation et la mise en cache (cache disque) des pages mémoires par le système d'exploitation (systèmes non-Windows uniquement).
\end{itemize}
\end{description}

\subsection[Environment de test]{Environment de test}

Dans la mesure ou ce travail a attrait aux reseaux informatiques, il serait couteux de déployer un réseau physique (besoin d'un grand nombre de machines dédiées). Un evironnement de test virtuel sera donc utilisé pour effectuer la preuve de l'efficacité du logiciel présenté.

Le projet présentera une solution en utilisant un logiciel Vmware, selon le budget a disposition on choisira un produit léger (Server, Workstation) ou un produit plus performant (ESX). Les offres concurrentes ne permettent pas de virtualiser un reseau aussi complexe (particulièrement au regard des reseaux virtuels)

L'environment de test devra comporter au minimum 10 machines:
\begin{itemize}
\item 3 clients “stations de travail” - les ordinateurs sur lesquels les explorateurs internet effectuerons leurs requêtes. Une diversité de systèmes d'exploitation est bienvenue.
\item 2 routeurs – chaqun sera connecté au réseau virtuel et a l'internet.
\item 5 “noeuds” représentant le maillage interne au réseau virtuel.
\end{itemize}

L'utilisation d'un reseau virtuel facilite le test de tolèrance de panne (on peut aisément ``tirer la prise'' de plusieurs machines a la fois, dans n'importe quelle séquence, et de manière reproductible par script)

De plus, bien qu'un environment virtuel soit dépendant des performances de la machine hôte, les preformances se dégradent au sein des machines virtuelles de façon linéaire avec leur nombre - VMware garantit l'ordonnancement équitable des ressources. Un rapport de proportion peut donc être établi de façon relativement précise.

\section[Implémentation]{Implémentation}
\subsection[Stockage disque]{Stockage disque}

Le stockage sur disque est effectué de la manière suivante:

\paragraph{Pickling}
Python propose la facilité de sérialiser les objets (pour être stockés) de facon rapide et facile avec la fonction ``pickle'' (littéralement, ``conserver dans du vinaigre'').

\begin{verbatim}
obj = new Object()
    Pickler.dump(obj, file)
\end{verbatim}

Dans le cas ou la fonction serait trop lente, python propose dans sa librairie standard le module cPickle - une implémentation de la fonction de pickle écrite en C, bien plus rapide.

\paragraph{Stockage des objets binaires}
Chaque élément mis en cache est écris sur le disque sous forme binaire. La structure de fichiers contenant le cache sera une arborescence ayant pour noeuds les N premiers bytes d'un ``hash'' du fichier (sous forme hexadecimale). Ainsi, pour une image exemple ``example.jpg'', Python nous donne le tableau de bytes correspondant au hash de l'objet:

On extrait les N premiers bytes intéressants:
\begin{verbatim}
bytes = [n:]
\end{verbatim}
On affiche en héxadécimal chaque byte indépendemment:
\begin{verbatim}
for(byte in bytes):
    print byte
\end{verbatim}
On insère la totalité de l'objet (toute l'image dans cet exemple) dans la structure de fichier, à l'emplacement ``[racine]/FA/85/E4/Image.jpg''. 

Une alternative au stockage dans le système de fichier serait de stocker les objets (sous forme ``pickled''), dans la base de données utilisée pour stocker les données de méta-information. 


\subsection[Stratégie de “fraicheur”]{Stratégie de “fraicheur”}
\subsection[Protocole HTTP]{Protocole HTTP}
La norme définisant HTTP propose plusieurs ports réseaux sur lesquels fonctionner. En pratique, un administrateur web peut décider de faire écouter son serveur Web sur n'importe quel port, il ne bénéficie pas en revanche des optimisations réseau dont le cache fait partie. Les ports HTTP par défaut que ce logiciel cachera sont:
\begin{description}
\item[80] Le port 80 est le port standard défini par le protocole HTTP.
\item[8080] Le port 8080 est le port alternatif au port 80 le plus utilisé, particulièrement pour les autres caches disponibles sur le marché. Il est donc interessant de conserver en cache le traffic destiné à ce port.
\end{description}

Le logiciel ne \emph{cachera pas} les données du protocole HTTPS - bien que le cryptage garantisse la sécurité des données même en cache, il est peu interessant de cacher des données dont un seul utilisateur possède la clé de décryptage\ldots Le cache HTTPS serait contre-productif au regard du cahier des charges (\ref{CahierDesCharges})

\paragraph{Headers HTTP spécifiques}
Le logiciel présenté ici rajoutera des headers HTTP aux requêtes sortantes, afin de pouvoir transmettre des meta-informations de requêtes, dans le but d'empêcher la création de boucles ou de récurser ``trop loin''

Pour éviter les boucles, il peut être intéressant de marquer les requêtes par une série d'identifiants de noeuds par lesquelle une requête spécifique est passée - Un noeud pourrait ainsi détecter les noeuds par lesquelle la requête est déja passée et ne pas leur envoyer la même requête une seconde fois.

Un autre header interessant serait le ``marqueur de récursion'' - une requête contiend un marqueur de récursion initialisé a N, chaque noeud décrémente N de 1 a chaque ``bond''. Les noeuds se contentent de pousser une requête avec une récursion de 0 ou négative sans s'occuper d'attendre la réponse ou de vérifier si l'objet est en cache.

\paragraph{Traitement des requêtes invalides}
Dans le cas ou la notification a un noeud pair prendrait trop de temps a "revenir" (lien internet coupé, machine indisponible...), le cache sert simplement la version la plus fraîche de l'objet demandé. Dans le cas ou une réponse ulterieure survient (le noeud interrogé a mis plus de temps a répondre qu'un autre), le cache met simplement l'objet a jour, qui est donc considéré "plus frais", et servira pour des requêtes ulterieures.

Le niveau de récursion doit être choisi avec soin - en effet, plus le niveau de récursion demandé sera élevé, plus le cache aura un \emph{hit-rate}\footnote{Ratio entre objet servi depuis le cache et objet servi depuis la source originale} élevé, mais plus le nombre de requêts croît rapidement. Il s'agit d'une croissance exponentielle, O(n(puiss) x)

Définir une stratégie de paramètrisation est donc cruciale, et dépend très fortement des conditions d'implementation phisique.

\subsection[Threading]{Threading}

Il n'est pas efficace pour un cache/proxy d'être limité par le nombre de processus - il est fort possible qu'un grand nombre de clients demandent des objets en cache, sur un grand nombre d'objets differents. Dans ce cas, il est imperatif d'avoir un modèle de \emph{threading} efficace, sans quoi les differents clients devraient attendre un temps inacceptable avant d'avoir une réponse, ce qui serait contre-productif (\ref{CahierDesCharges}).

\paragraph{Threads ``entrants''}
On implementera un thread par requète HTTP Entrante. Il est ainsi facile de servir un grand nombre de threads, dans la mesure ou la seule limitation est le nombre de locks que la hashtable peut servir.

On pourra augmenter dynamiquement le nombre de hashtables - plus on a d'objets syncronizés, plus le nombre de verrous possibles est grand (croit avec N de façon linéaire). Ce contour du mechanisme de verrou, potentiellement lent, doit être implémenté de façon sensible, afin de ne pas augmenter inutilement le nombre d'éléments cachés en mémoire.

\paragraph{Threads ``sortants''}
Chaque requête non satisfaite par le cache (la hashtable) doit êtresyn
 renvoyée (``recursed'') aux noeuds voisins, afin de ne pas aller chercher l'objet demandé trop loin.

Afin de ne pas inutilement utiliser des ressources systèmes en ``attente active'', il est bienvenu de découpler chaque appel HTTP en un thread séparé, qui ne sera notifié par la socket qu'une fois une réponse obtenue. Un fois une réponse obtenue, on ne manquera pas de tuer les threads écoutant encore sur d'autres caches voisins pour un même objet (puisqu'on a déja une copie de l'objet dans le noeud courant).

\subsection[Routage]{Routage}
\chapter[Applications]{Applications}
\section[Réseau Wifi a longue distance]{Réseau Wifi maillé a longue distance}

Dans les pays émergeants, un des pricipaux obstacles au déploiement de l'internet est le coût prohibitif des infrastrucutres fondamentales de liens point-à-point entre les differentes parties du pays.
En effet, déployer un réseau de type occidental requiert d'installer des câbles de fibre optique sur de longues distance, qui le plus souvent sont faiblement peuplées, et qui potentiellement traversent des terrains inhospotaliers (chaînes montagneuses, déserts \ldots).

\subsection[Réseaux herziens]{L'avantage des réseaux herziens}
Bien que déployer de l'infrastrucutre cablée soit trop coûteux dans une majorité de cas, le déployement d'antennes-relai pour une infrastructure internet est comparativement abordable.
Les antennes, particulièrement en terrain inhospitalier, posent cependant un problème: leur taux moyen de panne est bien plus élevé, de part la nature des antennes, exposées et sensibles aux éléments (pluie, neige, tempêtes de sable, mais aussi chaleur excessive, nuages de sautrelles \ldots). 

Dans ce contexte, un système distribué habituel ne fonctionne que très mal: les caches habituels partent du principe que bien que la bande passante soit limitée, les temps de latence sont bas et les noeuds sont généralement disponibles. Dans le cas de déploiement dans un millieu inhospitalier, la probabilité que la bande-passante soit le goulot d'étranglement diminue considérablement.

\paragraph{Réseaux point-à-points}
Le logiciel de cahce distribué présenté permet d'amoindrir ce problème: l'information est distribuée le long des noeuds, et il est possible de paramètrer le niveau de récursion. Un unique lien composé de plusieurs caches ``en série'' peut distribuer l'information au sein de chaque noeud, et ainsi tirer profit de la somme des ressources \emph{hardware} qui le compose.

\paragraph{Réseaux maillés}
Dans le cas d'un réseau maillé, plus interessant, chaque noeud possède plusieurs liens vers des noeuds alentours. Chaque noeud profite ainsi de la "proximité" relative de ses voisins pour aller y chercher, à moindre coût, les informations demandées par ses utilisateurs. En partant du postulat que les sites accèdés sont globalement les mêmes (Wikipedia, Google par exemple, seront vraisemeblablement consulté dans plusieurs écoles voisines avec une relativement haute fréquence), la proximité des noeuds, au sens ``nombre de liens à parcourir'', collabore à la qualité du service internet proposé aux utilisateurs.

\section[Accès internet par GPRS]{Accès internet par GPRS}

\subsection[Grande disponibilité]{Grande disponibilité d'antennes}
Dans le monde, les réseaux téléphoniques sont pervasif. Même dans les pays en voie de développment, bien que le niveau de vie moyen soit largement moins élevé que dans les pays occidentaux, les téléphones cellulaires sont très répandus.

Il est donc logique, dans une optique de distribution de conneciton internet, de tirer parti des infrastructures existantes afin d'amoidrir les coûts au maximum.

Il est tout a fait possible, voir facile, de coupler un module GPRS a un ordinateur a portée de réception d'une antenne téléphonique, et de créer à partir de celui-ci un réseau wifi, directionnel ou pas, afin de ditribuer plus avant la connection internet ainsi rendue disponible. 

Dans la mesure ou le système de cache distribué décrit dans ce texte est agnostique du mode de transmission ou de routage, il estr trivial d'en installer une copie sur l'ordinateur, devenu ``gateway'' internet, et de configurer les caches des noeuds voisins pour le considerer comme un cache pair. Il peut fournir de plus un point de routage vers le réseau internet externe. Un réseau maillé configuré avec un protocole intelligent (de type OSPF par exemple), peut tirer parti d'un tel routage.

\end{document}
